class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if(nums.size()==0||k==0) return {};
        deque<int> dq;
        vector<int> ans(nums.size()-k+1);
        int left=1-k,right=0;
        while(right<nums.size())
        {
            if(left>0&&dq.front()==nums[left-1])
            {
                dq.pop_front();
            }
            while(!dq.empty()&&dq.back()<nums[right])
            {
                dq.pop_back();
            }
            dq.push_back(nums[right]);
            if(left>=0)
                ans[left]=dq.front();
            left++;
            right++;
        }
        return ans;

    }
};
